TNotes.leetcode

Appearance

⏰0442. 数组中重复的数据【中等】

0442. 数组中重复的数据【中等】 ​

1. 📝 题目描述 ​

给你一个长度为 n 的整数数组 nums，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。

示例 1：

txt
输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

示例 2：

txt
输入：nums = [1,1,2]
输出：[1]

示例 3：

txt
输入：nums = [1]
输出：[]

提示：

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • nums 中的每个元素出现 一次 或 两次

2. 🎯 s.1 - 原地标记 ​

c
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    for (int i = 0; i < numsSize; i++) {
        int idx = abs(nums[i]) - 1;
        if (nums[idx] < 0) res[(*returnSize)++] = idx + 1;
        else nums[idx] = -nums[idx];
    }
    return res;
}
js
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
  const res = []
  for (const num of nums) {
    const idx = Math.abs(num) - 1
    if (nums[idx] < 0) res.push(idx + 1)
    else nums[idx] = -nums[idx]
  }
  return res
}
py
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for num in nums:
            idx = abs(num) - 1
            if nums[idx] < 0:
                res.append(idx + 1)
            else:
                nums[idx] = -nums[idx]
        return res
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)（不计结果数组）

算法思路：

  • 利用数组值在 [1,n] 的特点，将 |num|−1 位置取反
  • 若已经为负，说明出现过两次，加入结果